SherbyNet - /page/wikibook/entry.mu

Micron Document

Polytree

13.8 KB · ⇊ 9 parts · ⤓ Micron 13.8 KB · ⤓ HTML 32.5 KB

──────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────

top

In mathematics, and more specifically in graph theory, a polytreecite-ref-footnotedasgupta1999-1-0[1] (also called directed tree,cite-ref-footnotedeo1974206-2-0[2] oriented treecite-ref-3[3] or singly connected networkcite-ref-kp83-4-0[4]) is a directed acyclic graph whose underlying undirected graph is a tree. In other words, a polytree is formed by assigning an orientation to each edge of a connected and acyclic undirected graph.

A polyforest (or directed forest or oriented forest) is a directed acyclic graph whose underlying undirected graph is a forest. In other words, if we replace its directed edges with undirected edges, we obtain an undirected graph that is acyclic.

A polytree is an example of an oriented graph.

The term polytree was coined in 1987 by Rebane and Pearl.cite-ref-rp87-5-0[5]

Contents

• Related structures

• Enumeration

• Sumner's conjecture

• Applications

• See also

• Notes

• References

Related structures

• An arborescence is a directed rooted tree, i.e. a directed acyclic graph in which there exists a single source node that has a unique path to every other node. Every arborescence is a polytree, but not every polytree is an arborescence.

• A multitree is a directed acyclic graph in which the subgraph reachable from any node forms a tree. Every polytree is a multitree.

• The reachability relationship among the nodes of a polytree forms a partial order that has order dimension at most three. If the order dimension is three, there must exist a subset of seven elements x {\displaystyle x} , y i {\displaystyle y_{i}} , and z i {\displaystyle z_{i}} (for i = 0 , 1 , 2 {\displaystyle i=0,1,2} ) such that, for each i {\displaystyle i} , either x ≤ ≤ y i ≥ ≥ z i {\displaystyle x\leq y_{i}\geq z_{i}} or x ≥ ≥ y i ≤ ≤ z i {\displaystyle x\geq y_{i}\leq z_{i}} , with these six inequalities defining the polytree structure on these seven elements.cite-ref-footnotetrottermoore1977-6-0[6]

• A fence or zigzag poset is a special case of a polytree in which the underlying tree is a path and the edges have orientations that alternate along the path. The reachability ordering in a polytree has also been called a generalized fence.cite-ref-footnoteruskey1989-7-0[7]

Enumeration

The number of distinct polytrees on n {\displaystyle n} unlabeled nodes, for n = 1 , 2 , 3 , … … {\displaystyle n=1,2,3,\dots } , is

1, 1, 3, 8, 27, 91, 350, 1376, 5743, 24635, 108968, 492180, ... (sequence

A000238

in the

OEIS

Sumner's conjecture

Sumner's conjecture, named after David Sumner, states that tournaments are universal graphs for polytrees, in the sense that every tournament with 2 n − − 2 {\displaystyle 2n-2} vertices contains every polytree with n {\displaystyle n} vertices as a subgraph. Although it remains unsolved, it has been proven for all sufficiently large values of n {\displaystyle n} .cite-ref-footnotek-hnmycroftosthus2011-8-0[8]

Applications

Polytrees have been used as a graphical model for probabilistic reasoning.cite-ref-footnotedasgupta1999-1-1[1] If a Bayesian network has the structure of a polytree, then belief propagation may be used to perform inference efficiently on it.cite-ref-kp83-4-1[4]cite-ref-rp87-5-1[5]

The contour tree of a real-valued function on a vector space is a polytree that describes the level sets of the function. The nodes of the contour tree are the level sets that pass through a critical point of the function and the edges describe contiguous sets of level sets without a critical point. The orientation of an edge is determined by the comparison between the function values on the corresponding two level sets.cite-ref-footnotecarrsnoeyinkaxen2000-9-0[9]